/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/maximum-gap
   @Language: C++
   @Datetime: 19-04-03 13:24
   */

// Method 1, base sort, Time 151ms
class Solution {
public:
	/**
	 * @param nums: an array of integers
	 * @return: the maximun difference
	 */
	int maximumGap(vector<int> &nums) {
		// write your code here
		const auto min_max=minmax_element(nums.begin(),nums.end());
		const int min_base=*min_max.first, max_base=*min_max.second;
		const int base=sqrt(max_base-min_base)+1;
		vector<set<int> > vs(base);
		for(const int a:nums)
			vs[(a-min_base)/base].insert(a);
		int gap=0;
		for(int i=0, pre=INT_MAX; i<base; ++i)
			for(const int &a:vs[i]){
				gap=max(gap,a-pre);
				pre=a;
			}
		return gap;
	}
};


// Method 2, quick sort, Time 151ms
class Solution {
public:
	/**
	 * @param nums: an array of integers
	 * @return: the maximun difference
	 */
	int maximumGap(vector<int> &nums) {
		// write your code here
		sort(nums.begin(),nums.end());
		int gap=0;
		for(int i=1; i<nums.size(); ++i)
			gap=max(gap,abs(nums[i]-nums[i-1]));
		return gap;
	}
};
